package com.zjsru.oneDay202209;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * @Author: likew
 * @Date: 2022/9/28
 * 有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。
 *
 * 输入: k = 5
 *
 * 输出: 9
 */
public class GetKthMagicNumber {
    
    public int getKthMagicNumber(int k) {
        int[] nums = new int[] {3, 5, 7};
        PriorityQueue<Long> queue = new PriorityQueue<>();
        Set<Long> set = new HashSet<>();
        queue.add(1L);
        set.add(1L);
        while (!queue.isEmpty()) {
            long t = queue.poll();
            if (--k == 0) {
                return (int) t;
            }
            for (int x : nums) {
                if (!set.contains(x * t)) {
                    queue.add(x * t);
                    set.add(x & t);
                }
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        GetKthMagicNumber getKthMagicNumber = new GetKthMagicNumber();
        int k = 5;
        System.out.println(getKthMagicNumber.getKthMagicNumber(k));
    }
}
